public class HeapSort {
    public int[] sortArray(int[] nums) {
        heapSort(nums);
        return nums;
    }


    public void heapSort(int[] nums) {
        int len = nums.length;
        buildMaxHeap(nums, len-1);
        swap(nums, 0, len-1);
        int end = len - 2;
        while (end > 0) {
            maxHeapify(nums, 0, end);
            swap(nums, 0, end);
            end--;
        }

    }
    public void buildMaxHeap(int[] nums, int end) {
        for (int i = (end-1) / 2; i >= 0; --i) {
            maxHeapify(nums, i, end);
        }
    }

    /*小数一直下沉*/
    public void maxHeapify(int[] nums, int i, int end) {
        while (2 * i + 1 <= end) {
            int lson = (i << 1) + 1;
            int rson = (i << 1) + 2;  // 这里易错不加括号
            int large = i;
            if (lson <= end && nums[lson] > nums[large]) large = lson;
            if (rson <= end && nums[rson] > nums[large]) large = rson;
            if (i == large) {
                break;
            } else {
                swap(nums, i, large);
                i = large;
            }
        }
    }
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;

    }


}
